package hot;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lakersUp
 * @Classname
 * @Description
 * @Date 2022/4/2 9:27
 * @Version 1.0
 */
public class Hot437pathSum {
    int res=0;
    public int pathSum(TreeNode root, int sum){
        Map<Integer,Integer> map = new HashMap();
        map.put(0,1);
        dfs(map,root,sum,0);
        return res;
    }

    private void dfs(Map<Integer, Integer> map, TreeNode root, int sum, int curr) {
        if(root==null){
            return;
        }
        curr+=root.val;
        res+=map.getOrDefault(curr-sum,0);
        map.put(curr,map.getOrDefault(curr,0)+1);
        dfs(map, root.left, sum, curr);
        dfs(map, root.right, sum, curr);
        map.put(curr,map.getOrDefault(curr,0)-1);
        curr-=root.val;
    }
}
